//
// Created by Administrator on 2021/5/12.
//
#include <vector>
#include <iostream>
#include <stack>

using namespace std;

class Solution {
public:
    bool validateStackSequences(vector<int> &pushed, vector<int> &popped) {
        /** 利用条件：值不重复
         * 将 pushed 队列中的每个数都 push 到栈中。
         * 检查栈顶是不是 popped 序列中下一个要 pop 的值，
         * 如果是就把栈顶 while-loop  pop 出来。
        最后，检查不是所有的该 pop 出来的值都是 pop 出来了。
        */
        stack<int> st;
        int index = 0;
        for (int &i : pushed) {
            st.push(i);
            while (!st.empty() and st.top() == popped[index]) {
                ++index;
                st.pop();
            }
        }
        return st.empty();
    }
};

int main() {
    vector<int> push{1, 2, 3, 4, 5};
    vector<int> pop{4, 3, 5, 1, 2};
    Solution sol;
    cout << (sol.validateStackSequences(push, pop) ? "true" : "false") << endl;
    return 0;
}